package search.binary_search;

/**
 * 二分查找 有重复元素，查找第一个等于给定值的元素
 *
 * @author yeyangtao created at 11:36 2020/9/29
 */
public class BinarySearch1 {
    public static int binarySearch(int[] a, int value) {
        int size = a.length;
        int low = 0;
        int high = size - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value)
                high = mid - 1;
            else if (a[mid] < value)
                low = mid + 1;
            else {
                //等于的时候判断，如果mid是第一个肯定是第一个元素
                //其他情况判断 它前一个是不是也等于value
                //不等于说明当前就是第一个
                //等于的话 第一个肯定在low与mid-1之间
                if (mid == 0 || a[mid - 1] != value) return mid;
                else high = mid - 1;
            }
        }
        return -1;
    }
}
